package treeNode;

import java.util.*;

public class Solution10 {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>(); //存放 所有节点的父节点 key(子节点）->value（父节点）

    public List<List<Integer>> pathSum(TreeNode root) {
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queueNode = new LinkedList<TreeNode>();  //存放 所有的节点
//        Queue<Integer> queueSum = new LinkedList<Integer>();  // 遍历到该节点的所有 val的sum

        queueNode.offer(root);
//        queueSum.offer(0);

        //遍历 所有的节点  (虽然queueNode一开始没有所有节点，但是可以边遍历边插入嘛）
        while(!queueNode.isEmpty()){
            TreeNode  treeNode = queueNode.poll(); //把最开始的压出来
//           int sum = queueSum.poll()+treeNode.val; // 和
            if(treeNode.left==null&&treeNode.right==null){ //到达 叶子节点啦 ，遍历结束了，是时候收网了
                getPath(treeNode);
            }

            if(treeNode.left!=null){ //哈，你还有left ,那不行，得处理
                map.put(treeNode.left,treeNode); //treeNode。left的父亲不就是 treeNode吗，赶紧put,getPath要用
                queueNode.offer(treeNode.left);
//                queueSum.offer(sum);  //
            }

            if(treeNode.right!=null){
                map.put(treeNode.right,treeNode);
                queueNode.offer(treeNode.right);
//                queueSum.offer(sum);  //
            }


        }

        return ret;
    }

    /**
     * 获得 该node 路径下的 和 ，并把该路径 添加到 ret 中去
     * @param node
     */
    public void getPath(TreeNode node) {
        List<Integer> temp = new LinkedList<Integer>();
        while (node != null) {
            temp.add(node.val);
            node = map.get(node);  //获得该node的父节点
        }
        Collections.reverse(temp);
        ret.add(new LinkedList<Integer>(temp));
    }

    public static void main(String[] args) {
        TreeNode root = TreeNodeUtils.getTestTreeNode();
        System.out.println(new Solution10().pathSum(root));

    }

}
